#ifndef HASHTABLE_H
#define HASHTABLE_H

#include <vector>
#include <list>

using namespace std;

template <typename keyType, typename HashFunc>
class HashTable
{
private:
	struct Node
	{
		keyType key;
	};
	HashFunc hf;						//Hash function
	vector<list<Node>> data;			//The buckets
	int currentSize;					//Number og items in the hash table
	double loadFactor;
	int rehashCount;					//Number of rehashes performed

public:
	//Constructor
	explicit HashTable(int size=103, double load=1.0)
	{
		currentSize = 0;
		data.resize(size);
		loadFactor = load;
		rehashCount = 0;
	}

	//Copy constructor - shouldn't be needed, since the class uses no pointers, but just to be safe...
	HashTable(const HashTable<keyType, HashFunc>& h)
	{
		if(h != this)
		{
			this->hf = h.hf;
			this->currentSize = h.currentSize;
			this->loadFactor = h.loadFactor;
			this->data = h.data;
			this->rehashCount = h.rehashCount;
		}
	}

	//Assignment operator - shouldn't be needed, since the class uses no pointers, but just to be safe...
	const HashTable & operator=(const HashTable<keyType, HashFunc>& h)
    {
        this->hf = h.hf;
		this->currentSize = h.currentSize;
		this->loadFactor = h.loadFactor;
		this->data = h.data;
		this->rehashCount = h.rehashCount;
        return (*this);
    }

	//Destructor - shouldn't be needed, since the class uses no pointers, but just to be safe...
	~HashTable() {}
	
	//Returns the number of elements ("filled buckets", including seperate chaining) in the table
	int size() { return currentSize; }
	//Returns the number of buckets in the table (size of the vector)
	int buckets() { return this->data.size(); }
	//Returns the number of times rehashing has been performed.
	int reHashing() { return this->rehashCount; }

	//Inserts a value into the hash table. Returns true if succesful, or false if value already exists.
	bool insert(const keyType & key)
	{
		unsigned int i = hf(key) % data.size();
		list<Node>::iterator itr;
		for(itr = data[i].begin(); itr != data[i].end(); itr++)
			if((*itr).key == key)
				return false;
		Node n;
		n.key = key;
		data[i].push_back(n);
		currentSize++;
		if((double)((double)currentSize/(double)data.size()) >= loadFactor)
			rehash();
		return true;
	}

	//Remove value form the table. Returns true if succesful, or false if the value was not found.
	bool erase(const keyType & key)
	{
		unsigned int i = hf(key) % data.size();
		if(!data[i].empty())
		{
			list<Node>::iterator itr;
			for(itr = data[i].begin(); itr != data[i].end(); itr++)
			{
				if((*itr).key == key)
				{
					data[i].erase(itr);
					currentSize--;
					return true;
				}
			}
		}
		return false;
	}

	//Searches the table for a value. Returns true if the value was found, otherwise false.
	bool find(const keyType & key)
	{
		unsigned int i = hf(key) % data.size();
		if(!data[i].empty())
		{
			list<Node>::iterator itr;
			for(itr = data[i].begin(); itr != data[i].end(); itr++)
				if((*itr).key == key)
					return true;
		}
		return false;
	}

	//Rehashes the table, resizing the internal vector and copying all values to their new proper location.
	void rehash()
	{
		rehashCount++;
		vector<list<Node>> temp = data;
		unsigned int newSize = nextPrime(data.size()*2);
		data.clear();
		data.resize(newSize);
		vector<list<Node>>::iterator vecItr;
		list<Node>::iterator listItr;
		for(vecItr = temp.begin(); vecItr != temp.end(); vecItr++)
			for(listItr = (*vecItr).begin(); listItr != (*vecItr).end(); listItr++)
				data[hf((*listItr).key) % data.size()].push_back(*listItr);
	}
};

#endif HASHTABLE_H